package 图;

import java.util.ArrayList;
import java.util.Arrays;

public class Graph {
    /**
      vertexList 存储顶点的集合
     */
    private ArrayList<String> vertexList;
    /**
     * 存储图对应的邻结矩阵
     */
    private int[][] edges;
    /**
     * 表示节点的数目
     */
    private int numberEdges;

    /**
       定义一个布尔数组，记录某个节点是否被访问
     */
    private boolean[] isVisited ;

    public static void main(String[] args) {

        String Vertexes[] = {"1","2","3","4","5"};
        Graph graph = new Graph(Vertexes.length);
        /**
         * 把Vertexes[] = {"A","B","C","D","E"}中的元素赋值给vertexList
         */
        for (String vertex : Vertexes){
            graph.insertVertex(vertex);
        }
        /**
         * 添加边
         */
        graph.insertUndirectedEdge(0,1,1 );
        graph.insertUndirectedEdge(0,2,1 );
        graph.insertUndirectedEdge(0,3,1 );

        graph.insertUndirectedEdge(2,3,1 );
        graph.insertUndirectedEdge(2,4,1 );

        graph.insertUndirectedEdge(4,1,1 );

        graph.insertUndirectedEdge(4,3,1 );
        graph.showGraph();
        System.out.println("深度优先遍历");
        graph.dfs(graph.isVisited, 0);
    }
    /**
     * 构造器
     */
    public  Graph(int n) {
        /*
          初始化矩阵
         */
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        numberEdges = 0;
        isVisited = new boolean[5];
    }

    /**
     *
     * @param index 结点的下标值
     * @return 如果存在就返回对应下标，不存在返回-1
     */
    public int getFirstNeighbor(int index){
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i]>0){
                return i;
            }
        }
        return -1;
    }

    /**
     *
     * @param v1 前一个邻接节点
     * @param v2 下一个邻接节点
     * @return 如果存在就返回对应下标，不存在返回-1
     */
    public int getNextNeighbor(int v1,int v2){
        for (int j = v2 + 1; j < vertexList.size(); j++) {
            if (edges[v1][j] > 0){
                return j;
            }
        }
        return -1;
    }


    /**
     * 深度优先遍历算法
     * @param isVisited 判断该节点是否被访问过的布尔数组
     * @param i 节点的下标
     */
    public void dfs(boolean[] isVisited, int i){
        for (; i < getNumberOfVertex(); i++) {
            if (!isVisited[i]){
                //先访问一个节点并输出
                if (i < getNumberOfVertex() - 1){
                    System.out.print(getValueByIndex(i) + "->");
                }
                else {
                    System.out.println(getValueByIndex(i));
                }
                //将该节点设置为已访问
                isVisited[i] = true;
                //茶找该节点的第一个邻节点w
                int w = getFirstNeighbor(i);
                while (w != -1){
                    if (!isVisited[w]){
                        dfs(isVisited , w);
                    }
                    w = getNextNeighbor(i,w);

                }
            }
        }

    }
    /**
     * 返回节点个数的方法
     */
    public int getNumberOfVertex(){
        return vertexList.size();
    }
    /**
     * 返回边的条数的方法
     */
    public int getNumberOfEdges(){
        return numberEdges;
    }
    /**
     * 返回节点下标的方法
     */
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }
    /**
     * 返回v1 v2的权值
     */
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }
    /**
     * 显示图对应的矩阵的方法
     */
    public void showGraph(){
        /**
         * 下面的for循环等价于
         *         for (int i = 0; i < edges.length; i++) {
         *             for (int j = 0; j < edges[i].length; j++) {
         *                 System.out.println(edges[i][j]);
         *             }
         *         }
         * @param  link 等价于edges[i][j]
         */
        for (int[] link :edges){
            System.err.println(Arrays.toString(link));
        }

    }
    /**
     * 插入节点
     */
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }
    /**
     * 添加边
     * @param v1 表示点的下标
     * @param v2 表示相连的第二个点的下标
     * @param weight 表示权值
     */

    public void insertUndirectedEdge(int v1,int v2,int weight){
        edges[v1][v2] = weight;
//        edges[v2][v1] = weight;
        numberEdges++;
    }
    public void insertDirectedEdge(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numberEdges++;
    }

}

